SECD machine experiments begin - low level Shen to run on C

[Mark Tarver]

I've begun what will be the beginning of a long journey - to reduce
KLambda to something even more basic via the SECD machine. In case
you have never heard of it, the SECD machine (short for Stack-
Environment-Control-Dump) was invented by Peter Landin back in 1964 as
a model for mapping the evaluation of functional expressions to the
architecture of the digital computer. It was, as Bill and Ted would
say, most excellent. It is quite fascinating to emulate this in Shen.

The SECD machine figures in the 2nd edition of TBoS. Hakan has
already compiled Shen to bytecode, resulting in a platform 2x faster
than the Clojure port. I've posted a notice on this and made it
easier for people to find his work.

Mark

[Mark Tarver]

Yes; more modern is

A Rational Deconstruction of Landin’s SECD Machine
Olivier Danvy
2003

On Apr 12, 4:28 pm, Greg Spurrier <greg.spurr...@gmail.com> wrote:
> Fascinating stuff.
>
> Ishttp://comjnl.oxfordjournals.org/content/6/4/308.abstractthe canonical
> paper on the subject? Are there any other resources you would recommend for
> reading up on the subject?
>
> Thanks,
> Greg

[Raoul Duke]

> I've begun what will be the beginning of a long journey - to reduce
> KLambda to something even more basic via the SECD machine.

clueless question: it runs on C, but does it make interop with C easy?
i mean, lots of things are written in C but do not let me use C
libraries, apis, etc.

and in this day and age, i suspect that people would really rather be
able to interface with C++ although apparently that is a pain. i've
mostly only heard about that via http://felix-lang.org/

[Mark Tarver]

The SECD makes interop with any low level language much easier. Your
vote for C++ has Willi's endorsement; it is something he would like to
do. **He is hung up on the problem of heterogeneous lists and would
like to know how to formulate this in C++.** I would guess that some
kind of union type is required - something equivalent to the universe
type. However I don't know enough C++ to advise him here. Anybody
want to make a comment here?

If anybody wants to donate "Lisp in Small Pieces" to the project then
get in touch. We were trying to get this book through library loan
and failed.

There are roughly two ways to get from the SECD machine to C/C++.
Bottom up and top down. The top down method which I favour is to code
the SECD in Shen. The basic SECD is a very small program but not much
use. You have to beef it up to handle recursive defs and non-strict
application. But the result is still fairly small. When you get that
working, you recode it all using vector patterns without lists. When
that works, you remove the patterns and use destructive vector
operations. When that works you are not too far off C. Willi I
believe would prefer to work bottom up from C++.

This is at the moment fairly long term; the Ring has priority and is
of more immediate significance. However Hakan may have some
significant input here because he is far ahead on this curve. Last
time I heard he was in vipissana meditation in India.

Mark

[Mark Tarver]

If you want to try a flavour of the SECD machine in Shen, below is a
version I'm playing with which contains a REPL.

To try something out type

(repl)

and enter

[defun power [x y] [if [= y 0] 1 [* x [[power x] [- y 1]]]]]

hit a few returns - the program prints the states of the SECD - then
enter

[[power 2] 3]

(it's curried). After umpteen returns it will compute 8.

BTW re my previous post regarding representing heterogeneous lists in
C/C++, Willi is keen to know.

Mark

\\ SECD Machine with conditionals, recursion and arithmetic and a REPL
\\ copyright Mark Tarver, April 2013
\\ feel free to play with this
\\ usual disclaimers apply - work in progress

(synonyms stack (list ob)
environment (list (ob * ob))
control (list ob)
dump (list (stack * environment * control)))

(datatype globals

________________________________
(value *globals*) : environment;)

(datatype ob

X : number;
___________
X : ob;

X : boolean;
____________
X : ob;

X : symbol;
___________
X : ob;

X : string;
___________
X : ob;

________
[] : ob;

F : symbol; Params : (list symbol); Body : ob;
==============================================
[defun F Params Body] : ob;

X : ob; Y : ob; E : environment;
================================
[closure X Y E] : ob;

P : ob; Q : ob; R : ob;
=======================
[if P Q R] : ob;

X : ob; Y : ob;
===============
[X Y] : ob;

R : ob; X : ob; Y : ob;
=======================
[R X Y] : ob;

____________________________
reduce1 : (ob --> ob --> ob);

___________________________________
reduce2 : (ob --> ob --> ob --> ob);)

(set *globals* [])

(define repl
{--> A}
-> (let Read (do (output "~%> ") (input+ : ob))
Eval (trap-error (secd Read) (/. E "cannot evaluate this
expression"))
Print (print Eval)
(repl)))

(define secd
{ob --> ob}
[defun F Params Body] -> (update-global F (lambda-form Params Body))
X -> (evaluate [] (value *globals*) [X] []))

(define lambda-form
{(list symbol) --> ob --> ob}
[] Body -> Body
[Param | Params] Body -> [lambda Param (lambda-form Params Body)])

(define update-global
{symbol --> ob --> symbol}
F X -> (do (set *globals* [(@p F X) | (value *globals*)]) F))

(define evaluate
{stack --> environment --> control --> dump --> ob}
S E C D <- (do (output "S = ~R~%E = ~R~%C = ~R~%D = ~R~%" S E C D)
(read-byte (stinput))
(fail))
[Result] E [] [] -> Result
[X] _ [] [(@p S E C) | D] -> (evaluate [X | S] E C D)
S E [[if P Q R] | C] D -> (evaluate S E [P if @ Q R | C] D)
S E [@ | C] D -> (apply S E C D)
S E [X | C] D -> (evaluate [X | S] E C D) where (self-
evaluating? X E)
S E [X | C] D -> (evaluate S E [(lookup X E) | C] D) where
(isbound? X E)
S E [[lambda X Y] | C] D -> (evaluate [[closure X Y E] | S] E C D)
S E [[F X] | C] D -> (evaluate S E [X F @ | C] D)
S E [[R X Y] | C] D -> (evaluate S E [Y X R @ | C] D))

(define self-evaluating?
{ob --> environment --> boolean}
X E -> (or (string? X)
(number? X)
(boolean? X)
(empty? X)
(and (symbol? X) (not (isbound? X E)))))

(define isbound?
{A --> (list (A * A)) --> boolean}
X [(@p X Y) | _] -> true
X [_ | Y] -> (isbound? X Y)
X _ -> false)

(define apply
{stack --> environment --> control --> dump --> ob}
[[closure X Y E] Z | S] E' C D
-> (evaluate [] [(@p X Z) | E] [Y] [(@p S E' C) | D])
[if true | S] E [Q | _] D -> (evaluate S E [Q] D)
[if false | S] E [_ R | _] D -> (evaluate S E [R] D)
S E C D -> (evaluate (exec S) E C D))

(define lookup
{A --> (list (A * A)) --> A}
X [(@p X Y) | _] -> Y
X [_ | Y] -> (lookup X Y)
X _ -> X)

(define exec
{stack --> stack}
[R X Y | S] -> [(reduce2 R X Y) | S] where (dyadic? R)
[P X | S] -> [(reduce1 P X) | S] where (monadic? P))

(define reduce1
{(A --> A) --> A --> A}
P X -> (P X))

(define reduce2
{(A --> A --> A) --> A --> A --> A}
R X Y -> (R X Y))

(define dyadic?
{ob --> boolean}
X -> (element? X [= > < >= <= + - / *]))

(define monadic?
{ob --> boolean}
X -> (element? X [number?]))

\\ some stuff to try
\\ [defun factorial [x] [if [= x 0] 1 [* x [factorial [- x 1]]]]]
\\ [defun power [x y] [if [= y 0] 1 [* x [[power x] [- y 1]]]]]
\\ [[[lambda x [lambda y y]] a] b]

[Konrad Hinsen]

--On 27 avril 2013 04:39:25 -0700 Mark Tarver <dr.mt...@gmail.com> wrote:

> The SECD makes interop with any low level language much easier. Your
> vote for C++ has Willi's endorsement; it is something he would like to
> do. **He is hung up on the problem of heterogeneous lists and would
> like to know how to formulate this in C++.** I would guess that some

What exactly is the goal:

1) Implement Lisp-style lists containing Lisp values in C++

or

2) Implement heteregeneous lists whose elements can be any C++ data?

The first version should be straightforward by defining a "Lisp object"
type, so I suppose you want to do the second? That's not straightforward at
all, in particular if you want some kind of memory management.

> If anybody wants to donate "Lisp in Small Pieces" to the project then
> get in touch. We were trying to get this book through library loan
> and failed.

For those who read French, there is an updated edition that also happens to
be a lot cheaper:

Principes d'implantation de Scheme et Lisp
http://paracamplus.com/?CGIRunMode=book&urn=Cours/LiSP/4

Konrad.

[Mark Tarver]

I'll pass this over to Willi as he is the C++ person and this is his
puzzle.

Mark

On Apr 27, 1:53 pm, Konrad Hinsen <googlegro...@khinsen.fastmail.net>
wrote:

[w.r...@ntlworld.com]

I'm not too sure about your distinction.  I thought that the best
place to start would be with a C++ port of Shen, and maybe look at the
SECD in the future.
My problem is that a Lisp list is essentially heterogeneous and so is
a KLambda list.  C++ lists are type homogeneous and I don't see how to
define a general type
'Lisp Object' in C++ without performing my own memory management.

Willi

On 27 Apr, 13:53, Konrad Hinsen <googlegro...@khinsen.fastmail.net>
wrote:

[Willi Riha]

[Bruno Deferrari]

On Sat, Apr 27, 2013 at 12:48 PM, w.r...@ntlworld.com
<w.r...@ntlworld.com> wrote:
> I'm not too sure about your distinction. I thought that the best
> place to start would be with a C++ port of Shen, and maybe look at the
> SECD in the future.
> My problem is that a Lisp list is essentially heterogeneous and so is
> a KLambda list. C++ lists are type homogeneous and I don't see how to
> define a general type
> 'Lisp Object' in C++ without performing my own memory management.
>

Hi Willi.

Can you clarify what you mean by performing your own memory management
(you still need a GC which is not provided by C++, right?).

Regarding heteregeneous collections (warning, possibly dumb, naive and
not well-thought ideas), I would start with an abstract base class
'KLambdaObject' which defines as virtual methods every KLambda
primitive that takes a value as a parameter ('number?', 'cons?', 'hd',
'tl', etc) with their default implementations raising a type error
exception.

Then for each primitive type defined by the KLambda spec a subclass
would be defined that overrides the implementation of the methods that
make sense for that type (a pair type would redefine 'hd' and 'tl' to
return its first and second elements, and 'cons?' to return 'true').

KLambdaObject KLambdaObject::tl() { throw KLambdaTypeError("Not a cons"); }
KLambdaObject KLambdaCons::tl() { return my_tail; }

inline KLambdaObject tl(KLambdaObject &val) { return val.tl(); }

This is of course not very performant, but assuming there is no typing
information (something which is true for the current version of Shen)
I'm not sure about how to do better. Once typing information is
available then overloaded versions of functions could be defined, for
example:

inline KLambdaObject plus(KLambdaObject a, KLambdaObject b) { return
a.plus(b); }
inline double plus(double a, double b) { return a + b; }

> Willi
>
> On 27 Apr, 13:53, Konrad Hinsen <googlegro...@khinsen.fastmail.net>
> wrote:
>> --On 27 avril 2013 04:39:25 -0700 Mark Tarver <dr.mtar...@gmail.com> wrote:
>>
>> > The SECD makes interop with any low level language much easier. Your
>> > vote for C++ has Willi's endorsement; it is something he would like to
>> > do. **He is hung up on the problem of heterogeneous lists and would
>> > like to know how to formulate this in C++.** I would guess that some
>>
>> What exactly is the goal:
>>
>> 1) Implement Lisp-style lists containing Lisp values in C++
>>
>> or
>>
>> 2) Implement heteregeneous lists whose elements can be any C++ data?
>>
>> The first version should be straightforward by defining a "Lisp object"
>> type, so I suppose you want to do the second? That's not straightforward at
>> all, in particular if you want some kind of memory management.
>>
>> > If anybody wants to donate "Lisp in Small Pieces" to the project then
>> > get in touch. We were trying to get this book through library loan
>> > and failed.
>>
>> For those who read French, there is an updated edition that also happens to
>> be a lot cheaper:
>>
>> Principes d'implantation de Scheme et Lisp
>> http://paracamplus.com/?CGIRunMode=book&urn=Cours/LiSP/4
>>
>> Konrad.
>

> --
> You received this message because you are subscribed to the Google Groups "Qilang" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to qilang+un...@googlegroups.com.
> To post to this group, send email to qil...@googlegroups.com.
> Visit this group at http://groups.google.com/group/qilang?hl=en.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

--
BD

[Raoul Duke]

i am so clueless.

> a KLambda list. C++ lists are type homogeneous and I don't see how to
> define a general type
> 'Lisp Object' in C++ without performing my own memory management.

here i thought one /always/ had to do one's own memory management in
c++, for anything not on the stack. (having said that, there's Boehm's
GC; there's Boost Shared Ptr; there's probably commercial GCs; et.
al., all with their own horrendous drawbacks.)

[Raoul Duke]

p.s. http://www.lmgtfy.com/?q=heterogeneous+list+stl+c%2B%2B

i don't mean that to be super snarky, i seriously wonder if any of
those are at all useful.

[Konrad Hinsen]

Willi Riha writes:

> My problem is that a Lisp list is essentially heterogeneous and so is a
> KLambda list. C++ lists are type homogeneous and I don't see how to
> define a general type
> 'Lisp Object' in C++ without performing my own memory management.

You have to do your own memory management anyway in C++ if you want
garbage collection, which I think is inevitable for a Lisp
implementation. One choice is of course to adopt a GC library, there
are a few of them around, but I have not experience with any of them.

Something you could look at for inspiration is Lush:

http://lush.sourceforge.net/

It's a Lisp for numerical applications, which has both a high-level
layer with GC and a low-level layer without GC that is essentially C
in Lisp syntax.

Konrad.

[Mark Tarver]

I also found this.

http://stackoverflow.com/questions/8420744/how-to-create-a-heterogeneous-link-list-in-c-or-c

Mark

On Apr 27, 8:39 pm, Konrad Hinsen <googlegro...@khinsen.fastmail.net>
wrote:

[Mark Tarver]

I've now got 28 of the 46 KL primitives in the enhanced SECD. Very
insightful playing with this. A lot of stuff is not mentioned in the
sources I'm looking at.

I wouldn't like to attempt this program in either Haskell/ML or CL/
Scheme/Python. The former because the type system is too restrictive
and the need for constructors clutters up the program.The latter
because the lack of pattern-matching really makes the code hard to
follow. Imagine hacking this in CL.

(define evaluate
{stack --> environment --> control --> dump --> ob}
S E C D <- (do (output "S = ~R~%E = ~R~%C = ~R~%D = ~R~%" S E C D)
(read-byte (stinput))

(fail)) where (value *track*)

[Result] E [] [] -> Result
[X] _ [] [(@p S E C) | D] -> (evaluate [X | S] E C D)
S E [[if P Q R] | C] D -> (evaluate S E [P if @ Q R | C] D)

S E [[quote X] | C] D -> (evaluate [quote X | S] E [@ | C] D)

S E [@ | C] D -> (apply S E C D)
S E [X | C] D -> (evaluate [X | S] E C D) where (self-
evaluating? X E)
S E [X | C] D -> (evaluate S E [(lookup X E) | C] D) where
(isbound? X E)
S E [[lambda X Y] | C] D -> (evaluate [[closure X Y E] | S] E C D)

S E [[closure X Y E'] | C] D -> (evaluate [[closure X Y E'] | S] E C

D)
S E [[F X] | C] D -> (evaluate S E [X F @ | C] D)
S E [[R X Y] | C] D -> (evaluate S E [Y X R @ | C] D))

Mark

[Artella Coding]

This might be of interest to anyone building a C++ port : http://sourceforge.net/mailarchive/forum.php?thread_name=CANejTzqzVp2bsQga%2BK7bYtXU4Tp-v6YnGG2ixbDwx0mE_WY_sg%40mail.gmail.com&forum_name=ecls-list 

"A new C++ based implementation of Common Lisp based on the ECL CL code" by Christian Schafmeister