quasilyte / goism

Not a fan of Emacs Lisp? Hack Emacs in Go!

goism

Searching for Emacs Lisp alternative? Try hacking Emacs in Go!

Overview

Description

goism is Emacs package that makes it possible to use Go programming language instead of Emacs Lisp inside Emacs.

It provides Go intrinsics and emacs package to make it possible to control Emacs from your programs. Generated functions, methods and variables can be accessed from Emacs Lisp code.

Enjoy the increased type safety and curly braces!

How it works

Valid Go package is converted into Emacs Lisp bytecode.

Emacs goism package implements Go runtime, so translated code behaves as close to the specs as possible.

Different optimizations are performed during this translation, so it is not going to be any slower than "native" Emacs Lisp.

How to use it

See quick guide.

TODO: emacs package installation

Docs

• Quick guide (getting started)
• Translation specification
• Features that are not implemented
• goism implementation design

PreRelease2 is the current milestone.

To see what features are going to be implemented in near future, check out milestones.

Projects may contain additional information in "stashed" column.

Tags

• Compile Golang to Emacs Lisp bytecode
• Golang from Emacs
• Emacs Lisp alternative to extend Emacs
• Emacs Lisp as Golang compilation target
• "Go" emacs package

goism's Issues

Cross-package inlining

Currently, only emacs/rt package functions can be inlined into user packages.
Implementation has ad hoc nature.

To generalize inlining, particular strategy must be selected.
Some of them are listed below.

1. Always invoke AST parsing and conversions (for imports).
   (+) Convenient for the user.
   (+-) Can be sped up by alternative translation routine that searches for inlineable functions specifically.
   (-) Slower compilation speed.
   (-) No way to specify functions as "want it to be inlined" (useful for runtime). Inliner does not posses enough information to make correct decision in some cases.

2. Expect optional special file inline.go inside emacs/* packages.
   All functions defined at that file treated as candidates for inlining.
   (+) Significantly reduces amount of files that should be visited.
   (+) Provides explicit control over inlining.
   (-) Enforces code separation even if it is logically bound to other file.

Print and Println builtins optimization

Currently, rt.Print and rt.Println expect argument to be a list
and there is no way to make argument as "emacs-style &rest argument".
This results in inefficient list invocation applied to print/println arguments.

Adding support for &rest which holds unboxed lisp list does not seem like a good solution.

sexp.Walk function

opt.countUsages uses sexp.Rewrite only for readonly traversal.
sexp.Walk or sexp.Inspect should be provided to make such operations more efficient.

Optimizations for emacs package

Recognize functions that have special opcode in emacs.Call and replace function call with that.
Maybe instr_spec can be used as a map of function names.

emacs.Call("cons", a, b)
=>
stack-ref "a"
stack-ref "b"
cons

emacs.Call("list", 1, 2)
constant 1
constant 2
list2

...etc

Noinline/inline hints

emacs/rt.Panic should not ever be inlined.
Hack with empty composite statement is used {}, but it may stop working
when inliner will become smarter.

Also see: golang/go#12312

Variadic ops optimization

x + y + z translated to:

eval x
eval y
concat 2
eval z
concat 2

But it is better to emit:

eval x
eval y
eval z
concat 3

It also makes it easier to constant fold string concatenation sequences.
Note that lisp.Concat(x, y, z) generates optimal code.

This implementation is bad, but can give starting approximation:

func weakenConcat(form *sexp.InstrCall) sexp.Form {
	switch len(form.Args) {
	case 0:
		return sexp.Str("")
	case 1:
		return form.Args[0]
	}
	// This code should be re-written.
	args := make([]sexp.Form, 0, len(form.Args))
	for _, arg := range form.Args {
		arg = ReduceStrength(arg)
		if arg, ok := arg.(*sexp.InstrCall); ok {
			if bytes.Equal([]byte("concat"), arg.Instr.Name) {
				args = append(args, arg.Args...)
				continue
			}
		}
		args = append(args, arg)
	}
	form.Args = args
	form.Instr = instr.Concat(len(args))
	return form
}

Empty structs

Currently, empty structs are not implemented.
No technical reasons for that.

https://dave.cheney.net/2014/03/25/the-empty-struct

Non "=" assignments must evaluate lhs only once

x += 5 currently translated into x = x + 5.

From spec:

An assignment operation x op= y where op is a binary arithmetic operation is equivalent to x = x op (y)
but evaluates x only once.

Should be fixed.

Return on BasicBlock boundary

(dis-lambda (x y)
  (if (> x y)
      x
    y))

=>

byte code:
  doc:   ...
  args: (arg1 arg2)
0       stack-ref 1
1       stack-ref 1
2       gtr       
3       goto-if-nil 1
6       stack-ref 1
7       return    
8:1     return    

Return at 7 can be removed (note that at IR phase we do not have concrete jump addresses, so no excessive work is needed).

Simplify inserts inlineable function calls

sexpconv.Simplify inserts runtime functions calls; some of them can be inlined.
As a quick fix, inliner is invoked after the Simplify inside the compiler.
This should be re-considered later on.

Rename (shorten) identifiers to make code more idiomatic

Use sexp.Walk in sexp.IsReturning

Fix extern function call

call.go:

// return conv.callExprList(conv.makeFunction(fn.Sel, pkg.Name), args)
// Should be fixed along with cross-package inlining. REFS: #34.
panic(errUnexpectedExpr(conv, node))

Should be fixed.

Eliminate unreachable code

High level optimizer must eliminate dead code.

func Panic() {
  panic(0)
  return
  return
}

Currently, code illustrated above generates something like:

[Go-panic 0 nil]
  OpConstRef 0
  OpConstRef 1
  OpCall 1
  OpConstRef 2
  OpReturn
  OpConstRef 2
  OpReturn

Code after panic is "dead" and should be removed.

Cross basic-block peephole optimizations

Emacs optimizer does not optimize this correctly:

(defmacro bool (x) `(not (not ,x)))
(dis-lambda (x)
  (setq x (bool (and (> x 10)
                     (< x 20)
                     (/= x 15))))
  x)

0       dup       
1       constant  10
2       gtr       
3       goto-if-nil-else-pop 1
6       dup       
7       constant  20
8       lss       
9       goto-if-nil-else-pop 1
12      dup       
13      constant  15
14      eqlsign   
15      not       ;; <-- excessive
16:1    not       
17      not       
18      stack-set 1
20      return    

Argument thrashing

When function argument is to be used, it can be consumed instead of duplicated.

func f(x int) int { return x + x }

[x]
OpStackRef 0 [x x]
OpStackRef 0 [x x x]
OpNumAdd [x ?]
OpReturn 

// This one is better:
[x]
OpStackRef 0 [x x]
OpNumAdd [?]
OpReturn

Other simple case that illustrates the problem:

(defun f (x) (- x))

;;; disassemble:
;; dup
;; negate
;; ret

;;; optimized:
;; negate
;; ret

Maybe this rule should be generalized for any local variable.
First attempt:

When need to reference local and:
1) It's already on top of stack 
2) Even if it is consumed, there are other instances of it down the stack.
Do not emit OpStackRef and use that stack top instead.

Integer constants with at least 256 bits

Currently, sexpconv does not handle them and panics on inexact extraction.

Fixed-size arith

This ticket does not touch "unsigned int" question. They must be emulated.

Several options:

1. emulate fixed size behavior (overflow/underflow).
2. forbid anything except int, int64, float64 (and make rune alias for int64).
3. treat all fixed-size types as int64 or float64.

All options, except (1) are non-conforming to spec,
but more deep investigation needed.

Accept package name instead of full package path in main/translate_package

Leaf If statement (JMP collapsing)

package scratch
func add1(x int) int {
	if x > 100 {
		// Leaf If statement -- nested if with else which is 
		// the last statement of parental if.
		if x == 10 {
			x = 1
		} else {
			x = 2
		}
	} else {
		x = 3
	}
	return x
}

=>

byte code for Go-scratch.add1:
  args: (arg1)
byte code for Go-scratch.add1:
  args: (arg1)
0	dup	  
1	constant  100
2	gtr	  
3	goto-if-nil 3
6	dup	  
7	constant  10
8	eqlsign	  
9	goto-if-nil 1
12	constant  1
13	stack-set 1
15	goto	  2 ;; Should be "goto 4"
18:1	constant  2
19	stack-set 1
21:2	goto	  4
24:3	constant  3
25	stack-set 1
27:4	dup	 ;; Also excessive, but subject of another issue (#13)
28	return	

Not sure if leaf if term should be used. Unconditional jump collapsing seems more general and useful optimization.

Computable function complexity

lisp/function.Type should have a method to evaluate complexity.
This complexity will be used in sexp.Cost() function.

To solve this task, function table is needed.

Global variables

Generate varref and varset when referring to global variables.
bytecode.Compiler needs a map of all available globals.
Maybe it will also need types in future.

Unchecked panics

Instead of check+panic it is possible to use symbol constants to represent
panic sources.

;; Instead of this:
(defconst obj nil)
(if (null obj)
    (Go-panic ...))
  (aref obj 0))
;; Better to generate this:
(defconst obj nil-struct-ptr)
(aref obj 0)
;; Emacs will generate "wrong-type-argument arrayp nil-struct-ptr" error

Another example.
From spec: Assigning to an element of a nil map causes a run-time panic.

;; Assign special symbol for nil maps
(defconst m 'nil-map)
(puthash 'key 'val m) ;; Causes error "wrong-type-argument hash-table-p nil-map"

I have not found any clues about concrete error messages for run-time panics.
Probably it is conforming behavior to produce different error messages.

Compromise between error clarity and performance should be found.

Concurrency and multithreading

Go as a language provides concurrent programming primitives,
but in order to support them, implementation in emacs/rt is needed.

There are some projects that can be helpful, timp is one of them.
https://github.com/mola-T/timp

This issue is about planning; very long-term planning.

Void functions return optimization

func f() {}
func g() {
    f()
}

Output:

constant f
call 0
discard 1
constant nil
return

Should be:

constant f
call 0
return

Structs: basic support (no methods)

TODO:

• Struct types declaration
• Objects construction (via compound literals)
• Member selector expressions

Lisp intrinsics package lazy loading

emacsImporter initializes lisp.Package only when emacs/lisp package is imported.
This was equal to "lazy loading" in the past, but after emacs/rt package started to use emacs/lisp we always load it eagerly.

Now it is OK to load emacs/lisp package explicitly.

Implement methods support

Variable comments

Comments are collected for packages and functions, but not for variables.
Should be fixed.

This will require tu package translatePackage function modifications.

Restore design.md document

Recently, I removed design.md.
It should be restored from previous revisions.

In addition, it should be updated to reflect current design.

Slices

Runtime needs slices support.

String conversions

string('a') is a valid expression which should yield "a".
Rune may not be constant.

See: https://golang.org/ref/spec#Conversions.
"Conversions to and from a string type"

Multiple return values

Currently, multiple return values are not implemented.
Sexp nodes with multiple []Result are generated, but multi-value assignments
and return statements are not supported inside bytecode.Compiler.

Some notes:
a) It is quite efficient (and allocation-free) to use global variables for this.
Function assigns values to that variables, callee binds them to its locals.
Returning a fresh list/vector of results is impractical.
Emacs Lisp is single threaded, so there should be no data races.

b) Careful mapping should be used for results.
Two results should be packed into cons cell, all other sets (2+) are vectors.
This resembles ideas for struct objects.

Type assertions

It is nearly impossible to use emacs package without type assertions support.

Each type assertion must be translated into type check with panic on failure.

xs := emacs.Call("list", 1, 2, 3)

a := emacs.Call("car", xs).(int) // OK
b := emacs.Call("car", xs).(string) // Panics

Emacs Lapcode as compilation target

Emacs can perform optimizations on lap format.
It can be wise to generate that format instead of bytecode.

Struct conversions

Structs with identical underlying representations are convertible to each other.
https://golang.org/ref/spec#Conversions

Re-write runtime in Go

Instead of using Emacs Lisp to implement runtime support library for Emacs,
Go can be used.

lisp.Object `Interface()` method

It should be possible to coerce lisp.Object to Go-ish interface{} object (which can be further type-asserted into concrete Go type).

Implement function inlining

Inspect Emacs Lisp byte-opt.el and bytecomp.el

Some optimizations and bytecode generation techniques can be borrowed from there.

Invalid types of sexp forms

Some forms return invalid type when Type() method is called.
Several things require fixing:

• Predeclared functions should not use lisp.Object as return type
• type casts should be expressed in AST, not ignored

Slice get/set bound checks

Pointers

Primitive types in Emacs can not be "passed by reference" and there is no notion of "take address" operation there. To make it possible to support those operations, boxing is needed.

Currently, it is planned to implement boxing via cons cells, where car is the element "pointed to".
Boxing needed only for numerical types, other types are actually already boxed (structs, strings, ..).

Consequently, all numerical operations become slower due to boxing/unboxing issues.
It should be solved in two ways:

1. Eliminate boxing for a primitive if there is no address taking of variable it bound to. This should remove most of the boxing.
2. If boxing is needed and value is accessed more than X threshold, cache unboxed value and use it.

Update documentation to reflect recent changes

Named function results

Re-write IR related code

1. Need to replace lisp/ir. It can be either Go package that generates Emacs Lisp or goism translated Go.
2. Better format for ir/instr is needed. Comparison with bytes.Equal is not optimal.

Decompose/refactor bytecode/compiler

Rename project to goism

To make project name distinguishable.

Refactoring

1. sexpconv package needs great redesign
2. ir.Func should be replaced

Function calls with "ellipsis" (variadic)