ericbb

I think it's "Play": https://fonts.google.com/specimen/Play

(Replying to my own comment because I don't see a way to edit it.)

Another question I have is about recursion. Browsing through the code a little bit, I see loops and comprehensions are often used but I'm not sure I've seen a single recursive function. Is recursion something you've consciously tried to avoid and if so can you speak about the rationale on that topic?

> Maybe I'll post more tomorrow, if anyone is still around.

I can only speak for myself but I will definitely be around to read another post if you write one.

The design is fascinating and I'm very excited to see a new language that combines functional, relational, and reactive elements.

One design choice that I'm particularly interested in is your choice to fix the set of possible values in a way that supports generic value introspection and orthogonal persistence. There are clear benefits but some costs include possible obstacles to abstraction / modularity and also extensibility. I'm wondering how you see these trade-offs.

Here's one I made: http://norstrulde.org/ilge10/

The language is based on Scheme and Common Lisp.

The instruction set is derived from one described in the book Paradigms of Artificial Intelligence Programming by Peter Norvig.

The concurrency primitives are inspired by Erlang.

It's implemented in (old-fashioned) JavaScript but the compiler is self-hosting.

Thanks for the detailed response!

My point was that the beginning of foo() is compiled to the following (by my compiler):

    push   rbp
    mov    rbp,rsp
    lea    rax,[rbp+0x10]
    mov    QWORD PTR [rbp+0x10],rax

Instead of passing the struct in registers (rdi, rsi, rdx) or passing a pointer to the object (pass by reference), the caller places the object on the stack and the callee knows where to find it just based on the type of the function (it's at [rbp+0x10]).

On the other hand, if you delete the c field from the struct type, then the beginning of foo() looks like this:

    push   rbp
    mov    rbp,rsp
    sub    rsp,0x10
    mov    rax,rdi
    mov    rcx,rsi
    mov    rdx,rcx
    mov    QWORD PTR [rbp-0x10],rax
    mov    QWORD PTR [rbp-0x8],rdx
    lea    rax,[rbp-0x10]
    mov    QWORD PTR [rbp-0x10],rax

In that case, the struct was passed in via registers rdi, rsi (similar to tom_mellior's example) and subsequently copied to the stack (at [rbp-0x10] this time).

So, in neither case would I consider it "pass by reference" because neither leads to a pointer to the x object being passed in as an argument.

It's interesting to learn that Windows does it differently and does in fact use what I'd call "pass by reference". The only ABI I'm (somewhat) familiar with is Linux x86-64.

Your point about the annoying limitations on return values is a good one too. I had the thought at one point that it'd be possible to uniformly use structs with just one field instead of typedefs but the limitations on return value calling conventions mean that the two alternatives do not lead to equivalent code, surprisingly.

Haven't you misinterpreted "pass by reference" as "pass on the stack"?

(In the following program, I'd say that x is passed on the stack but not passed by reference.)

    #include <stdio.h>
    #include <stdlib.h>

    struct example { void *a, *b, *c; };

    void foo(struct example x)
    {
        x.a = &x;
        if (x.a != NULL) puts("In foo(), x.a is not NULL.");
    }

    int
    main(void)
    {
        struct example x = { .a = NULL };
        printf("sizeof(x): %lu bytes (%lu bits).\n", sizeof(x), 8 * sizeof(x));
        foo(x);
        if (x.a == NULL) puts("In main(), x.a is NULL.");
        return 0;
    }

Related: Computation and State Machines by Leslie Lamport (https://www.microsoft.com/en-us/research/publication/computa...).

For people reading this thread who want to better understand the distinctions between files, file descriptions, and file descriptors, I recommend Michael Kerrisk's book The Linux Programming Interface, which has great coverage of this topic.

With the C-c issue specifically, I don't think that emulator throughput is the most likely culprit.

It could be that the emulator is not handling inputs fairly: maybe it tries to process all available input from the pseudoterminal before processing the next batch of keyboard input. Or it could be that the pseudoterminal (kernel driver) is not configured to send the signal as expected. Or it could be that the process you're trying to interrupt is not responsive to the signal.

I maintain a terminal emulator that is not optimized at all and I just tested interrupting a process that was dumping one gigabyte of text to the screen. The interrupt was handled instantaneously.

I think that M-expressions are quite interesting but I'll just make a few concrete points here.

> if we want (quote x) it looks as if we have to write: ... quote[x]

I think that you could just write X in that case. Uppercase text was for symbolic atoms.

Also, you didn't mention conditionals:

M-expressions:

    ff[x] = [atom[x] → x; T → ff[car[x]]]

S-expressions:

    (defun ff (x) (cond ((atom x) x) (T (ff (car x)))))

The semicolon and the infix arrow have the benefit of reducing the need for parentheses in that case. And you can avoid writing "defun" and "cond".

When I mentioned "general recursive functions", I was thinking about systems that define functions using a system of functional equations rather than using a lambda term.

Example:

    odd 0 = False
    odd n = even (n - 1)
    even 0 = True
    even n = odd (n - 1)

I think "rewriting system" is something similar. (I'm not an expert in this stuff so I'm providing hints for further reading more than anything else).

In these systems, recursion is "built in" to the formal language itself.

On the other hand, lambda calculus does not have recursion "built in". All variables are bound by function application so it is not possible to have recursive bindings like you see in these recursive function systems. You can define recursive functions using mechanisms like the Y combinator but these work by reconstructing something over and over as the computation evolves. It's different.

In McCarthy's paper, there is a system of toplevel recursive functions and there is a LABELS form that behaves in a similar way. Lambda calculus has neither of these.

One resource that describes recursive function systems of the kind I'm thinking of is the book "Lambda-Calculus and Combinators, an Introduction" by Hindley and Seldin (especially chapter 4).

> `lambda` and function application alone are Turing-complete, as McCarthy would have known. The credit here belongs with Turing and Church, not McCarthy. `atom`, `cons`, `car` and all the rest are just icing on the cake of the lambda calculus when it comes to computability.

This point reminds me of something interesting that I noticed recently despite having been familiar with basic LISP ideas for a long time.

If you carefully read McCarthy's original presentation of LISP, you can see that he seemed to be influenced at least as much by Kurt Gödel's work as by Alonzo Church's work.

In Church's lambda calculus, functions are abstract values that can only be used by means of function application. LISP evolved toward this style over time, but in the early history of LISP, functions were not abstract values but were represented by encoding into S-expressions. This encoding process resembles Gödel numbering.

Also, recursion arises in a different form in lambda calculus than it does in the approach to computability that is based on general recursive functions. Again, I think that LISP is closer to Gödel here than to Church.

I like this one even better:

    $ cat test.c
    void _start(void)
    {
        __asm__(
            "movabsq $6278066737626506568,%rax\n\t"
            "movq %rax,-32(%rsp)\n\t"
            "movl $1684828783,-24(%rsp)\n\t"
            "movw $10,-20(%rsp)\n\t"
            "movq $1,%rax\n\t"
            "movq $1,%rdi\n\t"
            "leaq -32(%rsp),%rsi\n\t"
            "movq $13,%rdx\n\t"
            "syscall\n\t"
            "movq $60,%rax\n\t"
            "movq $0,%rdi\n\t"
            "syscall");
    }
    $ gcc -nostdlib -static -Os -o test test.c && strip test && ls -lgG test
    -rwxr-xr-x 1 864 Sep 28 14:22 test

864 bytes! :)

I always use dynamic linking but I thought it'd be fun to try making a small, static hello-world. The following assumes x86-64 Linux (and is a total hack that "works for me" NO WARRANTY!).

    $ cat test.c
    static int sys_write(int fd, const void *buf, unsigned long n)
    {
        asm("mov $1,%rax; syscall");
    }
    
    static void sys_exit(int status)
    {
        asm("mov $60,%rax; syscall");
    }
    
    void _start(void)
    {
        char s[] = "Hello, World\n";
        int r = sys_write(1, s, sizeof(s) - 1);
        sys_exit(r == -1 ? 1 : 0);
    }
    $ gcc -nostdlib -static -o test test.c && ls -lgG test
    -rwxr-xr-x 1 1480 Sep 28 11:47 test

More to the point of your question, if you want to see the effect you're looking for, I think you need to link to a libfoo.a library that includes some module.o that your program doesn't use.

Yes, I think I see your point. If I may put it in my own words, I think you are talking about "dynamic recursive activation" throughout this thread.

I don't mean to disagree with the point you are making! It's a valid point.

However, I would like to emphasize that some languages have syntactic properties that complicate things a bit and I feel that a comment about how things "should" be really ought to be qualified by something like, "in a mainstream Java-like language".

Consider the simply-typed lambda calculus, or Martin-Löf type theory. These languages don't allow general recursion but it's not because they are always poorly implemented!

That's an excellent question! :)

In my language, there is no special global scope for variables; every program is basically one giant (extended and sugared) lambda calculus expression.

I do use lambda-lifting so that in the C code I generate, there is a C function in the global C namespace that is called to execute an object-language function but object-language functions also have closure environments so any kind of self-reference needs to include both the global C function and the closure environment for that particular closure.

Note that my language does support modularity (breaking programs into multiple files, basically). However, the mechanism for referring to "packages" (stuff in other files) uses a separate name system.

I agree that languages that bind all functions in a global scope can easily use that global scope to resolve recursive references. It's also easier when your language supports variable assignment and destructive updates of data structures. But my language doesn't support those things either. :)

Addendum: By the way, you mentioned Java, Python, and Ruby, which are all object-oriented. Of course, the recursion among methods in those languages arises in a way that's very similar to passing a callee as a hidden argument. In OO languages, the hidden argument is "self" or "this"!

Matt Might's site has some pages on this topic:

http://matt.might.net/articles/books-papers-materials-for-gr...

http://matt.might.net/articles/intro-static-analysis/

http://matt.might.net/articles/partial-orders/

I definitely struggled to find a satisfying approach to recursion in my own current language project. What I'm doing right now is passing the closure value of the callee as a hidden first argument to every call. Nonrecursive functions just ignore that argument but recursive functions can always call themselves via that hidden argument.

It doesn't allow you to support syntactic mutual recursion but it's easy to do and can be implemented without data modification at any level.

I'm not sure what you are trying to achieve by using the infinite loop. There's a more direct way.

    void free_circularly_linked_list(struct node *head)
    {
      struct node *a = head->next;
      while (a != head) {
        struct node *b = a->next;
        free(a);
        a = b;
      }
      free(head);
    }

Great example, by the way!

I was surprised to read that x64 apparently doesn't allow pushing or popping 32-bit values. I have a language that uses 32 bits as the basic unit for all values and I'm working toward x64 code generation. Should I just promote values to 64 bits and waste half the stack? Should I use mov instructions instead of push/pop? What solutions are other compiler-writers using?

See the RISC-V User-Level ISA Specification v2.0 [1]. It's more detailed but still fairly easy reading.

[1] http://riscv.org/specifications/

That's funny. I was thinking isomorphism because you postulate an inverse, which homomorphisms don't always have. But the identity doesn't depend on f being invertible. You could just have a rule:

If f is a homomorphism with respect to r, then reduce(r, map(f, l)) = f(reduce(r, l)).

The rule can be proven without reference to an inverse for f so isn't it enough to just add such a rewrite rule to your optimizer? (Now I'm not sure what the inversion trick accomplishes?).

> Always curious to follow people doing compiler work; loop me in, yeah?

norstrulde.org and twitter.com/ericbb

> "there might or might not be an algebra in which f acts as a homomorphism, and, even if there is, you may not have the transformations you need to determine it!"

To my way of interpreting it, the algebra is determined by r, which is given. You might not know whether f is a homomorphism with respect to r and it'd be tricky to figure that out by inspecting the definitions for f and r but if you have a table built in advance that characterizes functions in relation to each other (incr is a homomorphism with respect to max, etc.), then you can drive your rewrite engine using that table... So I wouldn't say that you want to use transformations to determine if f is a homomorphism but rather that you want to use the fact that f is a homomorphism to decide which transformations are applicable. Does that make sense?

Edit: I guess, more generally, you could have a relation with the form homomorphism(f:a->b, q:a->a->a, r:b->b->b) which justifies the transformation reduce(r, map(f, l)) -> f(reduce(q, l)).

This approach is strongly reminiscent of abstract algebra; for example, the Map-Reduce Transformation example seems to be(?) justified exactly when f is an isomorphism over r.

I've been thinking along somewhat similar lines but I've been looking at it from the perspective of introduction and elimination rules, as found in type theory. If your compiler can find a transformation that brings an intro form and an elim form together, then you can apply the computation rule to remove both from the program. My motivation is to remove allocations that aren't really essential. (I do have a functional language compiler that I work on but it doesn't implement any optimizations yet).

Another interesting idea that seems related is from a Philip Wadler talk[1] I saw which discusses how normalization can be used to achieve something like your "hypothetical inverses", which should always be eliminated from the final result.

> These transformations might only be useful in obvious optimization scenarios (cases that no programmer would intentionally create).

I would be surprised if that turned out to be the case.

[1] "Everything Old is New Again: Quoted Domain Specific Languages" https://www.youtube.com/watch?v=DlBwJ4rvz5c

Here's one that might interest you.

Generating Good Syntax Errors http://research.swtch.com/yyerror

I don't immediately see why he is not just using NULL for nil but Interim is nonetheless more conventional than it may seem. It does use nil for '() (see [1]) and it evaluates (car nil) to nil and (cdr nil) to nil just like Common Lisp does. The last element of a list may be nil because list elements always appear in car positions whereas it is always the cdr position that one checks to identify the end of the list. If you walk a list without checking for nil, then you will appear to find a list that ends with an unending sequence of nil elements (as is the tradition!). For example, try (third nil) in Common Lisp; you will see a result of nil and no error.

[1] https://github.com/mntmn/interim/blob/master/sledge/alloc.c#...

I was thinking that some people would want to figure it out for themselves so I didn't want to spoil the challenge for them... I kind of hoped someone else would post the solution.

Anyway, here is a solution: http://play.golang.org/p/Mg8x7sJ-hR

In other words, just insert the following line:

    type int string

The thing is, "int" is not a reserved word in Go. It's just a predeclared binding. You can rebind it -- even use "int" as a local variable name, like so: http://play.golang.org/p/0_iTzkg-5m

There are other interesting cases. For example,

    var true = false // Perfectly valid Go code!

I think of it as a prank because you could sneak such a line into somebody's code and the compiler would not help them realize what had happened, it would just complain about a lot of nonsense like 1 not being an int. In the "var true = false" example, there would not even be a compiler error, you'd just get baffling runtime errors.

For a list of all the predeclared identifiers, see here: http://golang.org/ref/spec#Predeclared_identifiers

Ah, perfect. Thank you.

By "rationale" I was thinking more along the lines of "here is the reason we chose to do it this way" not just "here is the way we chose to do it".

Well, you could take the position that types that permit modification should not be allowed as keys but then you would not allow arrays as keys, which Go does allow. Check this out: http://play.golang.org/p/kocW1BjTco

Another approach to take, which I think could be quite useful, is that if you use something modifiable as a key, then the map takes a snapshot of it when you perform the insert. That way, I can go and modify the key after the insert and any time thereafter if I look for the same sequence of integers, the map will find the associated value.

The problem here is that, in a language like Go, where pointer values are significant (contrast with Haskell, where two lists allocated separately but having the same contents are indistinguishable), you sometimes want to use pointer identity as the key so maybe it's hard to have it both ways.

Oh well. It's just something that surprises someone like me, who has grown accustomed to more value-oriented languages.

This trick fits more into the "prank" category.

    package main
    
    import "fmt"
    
    // <Add one short line of valid Go code here>
    
    func main() {
    	var n int = 1
    	fmt.Println(n)
    }
    
    Compiler: "prog.go:8: cannot use 1 (type int) as type int in assignment"

Here's a trick that I expected to work but doesn't. Would be interested to hear the rationale if anyone knows it.

    m := map[[]int]int{}