Author Topic: Lisp in Basic  (Read 208253 times)

0 Members and 3 Guests are viewing this topic.

RobbeK

  • Guest
Re: Lisp in Basic
« Reply #705 on: August 23, 2014, 03:17:33 PM »
Mike,

"1. Show me the Scheme that has looping in it. I want to see its commands and their syntax."

I gave you a link to the official r5rs Standard - (attached) ,
I also asked you what "a pure Scheme" means : is it the one of Sussman and Steel (?) , the original or what ? you did not answer and If you have those documents, please give the links and I will read these.

 2.  I will add the looping only based on what I will see in at least one such Scheme available on the net.
ANY scheme I know has "named let" :

------------------------------------

  "Named `let'" is a variant on the syntax of let which provides a more general looping construct than `do' and may also be used to express recursions. It has the same syntax and semantics as ordinary `let' except that <variable> is bound within <body> to a procedure whose formal arguments are the bound variables and whose body is <body>. Thus the execution of <body> may be repeated by invoking the procedure named by <variable>.

(let loop ((numbers '(3 -2 1 6 -5))
           (nonneg '())
           (neg '()))
  (cond ((null? numbers) (list nonneg neg))
        ((>= (car numbers) 0)
         (loop (cdr numbers)
               (cons (car numbers) nonneg)
               neg))
        ((< (car numbers) 0)
         (loop (cdr numbers)
               nonneg
               (cons (car numbers) neg)))))   
          ==>  ((6 1 3) (-5 -2))

--------------------------------------------  from MIT   (p.s. the "named let" easily permits to define (while ) (until ) etc ...

3. Give me the Scheme names and syntax for (tan), (cotan), (sqrt), (pow) and (mod) and I will immediately add them to BL.

I do not need those (it was John who told not to spend much time on these - I did not spend any time on them, and just wrote what I needed) - everything is there that these can be constructed from what's available (I gave an example of (sqrt . ))- what is NOT available is any mechanism that will allow iteration that's the crucial point imho --

The examples I gave are compares -- because nothing compares to itself -- it's not about CL has that , or ExOsChEmE has this , it's about the importance of things - Recursion is perfect for mathematics , the formulae are even more compact , but not for program flow -- 

btw : your answer from 10th this month
---------------

@Rob:

Thanks for reminding me about (do). In fact I'm keeping it in mind. I'm simply waiting for when John finds a little time to get acquainted with the Scheme vocabulary to tell me that there's no (print) in there but rather (display), and that there's not only (for-each) in there but also (do)

---------------------------------






.

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #706 on: August 23, 2014, 03:24:04 PM »
:-\  I had a bad feeling about changing that. Please put it back the way it was.

On the contrary, John,

If #t and #f is a natural and canonical way for Scheme to denote its TRUE and FALSE (nil) then we'd better change BL's symbols to match.

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #707 on: August 23, 2014, 04:18:40 PM »
Thanks for the feedback, Rob.

"1. Show me the Scheme that has looping in it. I want to see its commands and their syntax."
I gave you a link to the official r5rs Standard - (attached) ,
I also asked you what "a pure Scheme" means : is it the one of Sussman and Steel (?) , the original or what ? you did not answer and If you have those documents, please give the links and I will read these.
 2.  I will add the looping only based on what I will see in at least one such Scheme available on the net.
ANY scheme I know has "named let" :

------------------------------------

  "Named `let'" is a variant on the syntax of let which provides a more general looping construct than `do'....

Quote from: Mike
@Rob:
Thanks for reminding me about (do). In fact I'm keeping it in mind. I'm simply waiting for when John finds a little time to get acquainted with the Scheme vocabulary to tell me that there's no (print) in there but rather (display), and that there's not only (for-each) in there but also (do)

This isn't entirely correct.

Please take a look at the attached picture which is a snippet of your own and note the red squares. In my opinion, a "library" is an extension housed in a module external to the language's engine. It's like GetTickCount() becoming available to you only when you load kernel32.dll. Until then, you can rely only on BASIC's internal TIMER.

The red squares are arousing a very strong suspicion in me that all this looping rather comes from a library extension of Scheme language but is not its intrinsic feature.  I think I already expressed it in this thread but I don't remember anybody confirm or refute my suspicion.

So you ask me to include non-standard library features in the main engine of the language ignoring at the same time my inquiries about its standard features  ( tan, cotan, mod, etc) that are still missing from there. You're discarding them as irrelevant for your current work but I can hardly discard them either because it's a complete language that I'm trying to finalize.

Can you confirm again that your example documentation on looping pertains to Scheme's vocabulary proper and not to the Scheme language extensions? I need to know it definitevely to take a decision how to host them in BL code; i.e. whether they should go in the main keyword hash table automatically on load or rather be loaded only in response to a command line switch or parameter like any extension would normally load in other languages.

Thanks for your help.

.
« Last Edit: August 23, 2014, 04:40:38 PM by Mike Lobanovsky »

RobbeK

  • Guest
Re: Lisp in Basic
« Reply #708 on: August 24, 2014, 12:40:21 AM »
Hi Mike,

Yes, it is library syntax , and so is (let ) (let* ) (and ) (or ) (cond ) (case ) which are present in this Scheme etc etc ,

Furthermore from this document :

It is required that every implementation of Scheme support
all features that are not marked as being optional
. Implementations are free to omit optional features of Scheme
or to add extensions, provided the extensions are not in
con ict with the language reported here. In particular,
implementations must support portable code by providing
a syntactic mode that preempts no lexical conventions.

Documentation from INRIA  (http://en.wikipedia.org/wiki/French_Institute_for_Research_in_Computer_Science_and_Automation )

There are people that find it difficult to accept Peano’s rule of inference.
Therefore, let us linger a little on it. Equation 5.1 is true for n=0, since this
is the trivial case of our demonstration. It is also true for n=1, since it is
true for n=0, and we have demonstrated that it is true for (n+1) whenever
it is true for n. It is also true for n=2, since it is true for n=1, and we
demonstrated that it is true for (n+1), if it is true for n. Got the idea?
In the Algorithm Language Scheme there are three ways to perform in-
terations, and inductions, to wit:

do-loop Below you will find how to define factorial using a do-loop.
1:=> (define (fact n)
(do ( (i 1 (+ i 1)) (acc 1 (* i acc)) )
( (> i n) acc) ) )
fact
1:=> (fact 5)
120


Named let
1:=> (define (factorial n)
(let iter ( (i 1) (acc 1) )
(if (> i n) acc
(iter (+ i 1) (* i acc)) )) )
factorial
1:=> (factorial 5)
120


Tail recursive function
1:=> (define (tail-fact i n acc)
(cond ( (> i n) acc)
(else (tail-fact (+ i 1) n (* i acc)) )) )
tail-fact
1:=> (define (fact n) (tail-fact 1 n 1))
fact
1:=> (fact 5)
120

It may be the pure no-library "syntax" refers to the original Sussman / Steel / etc experiment which I think contained no loop mechanism and in those days was named Schemer - but personally I never would use such , unless in a masochistic mood.

best Rob

Hi John,

Do you have contact with Mr Sussman ?  (i think to remember mentioning him).
You can ask him -- he is one of the important members of the Scheme standard committee.

best Rob

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #709 on: August 24, 2014, 12:44:13 AM »
Based on the Lamer's Guide to Scheme (which is exactly my current level) that John has provided earlier in this thread, there are no ways to express iteration in Scheme per se other than through recursion:

Quote from: Scheme Programming #1
Scheme has no while-loops or for-loops. In Scheme a similar effect is achieved by simply letting a function call itself.
Quote from: Scheme Programming #2
Scheme is very odd in one sense, it has no expressions designed for looping, repeating or otherwise doing something more than once at a general level.

Iterative recursion and looping over lists are performed in canonical Scheme with the instruments that are already available in BASIC Lisp: named and anonymous lambdas, if and cond clauses, and for-each and map procedures. Anything extra to these is regarded as syntactic sugar and is provided in a language extension library for ease of use for less recursively-minded (call it less introspective hehe) programmers.

There is however one important circumstance that the BASIC Lisp interpreter will never be able to provide:
Quote from: Scheme Programming
... whenever a function calls itself in such a way that the same effect can be implemented by a loop or iteration, Scheme guarantees that the compiler will rewrite it to a loop at the machine-code level, so you will never run out of stack space or need useless time to call procedures when what you try to do can be rewritten to a loop ...

(Rob and Charles, I wonder what the algorithm may look like to programmaticaly analyze a Scheme recursive procedure and unroll/fix/recode it automatically into a loop?)

So now I'm adding Scheme's base functionality that's still missing in BASIC Lisp which is:

-- radian-based trigonometry: tan and cotan, and also arc and hyperbolic trig in the languages where it is available (FBSL has it all intrinsically, not sure about SB);
-- power functions: sqrt and expt (FBSL has it all intrinsically, however SB's POW(n) is in fact POW10(n) only);
-- division functions: modulo and remainder;
-- rounding functions: floor (as it should be, not as it is now), ceiling, round, truncate, and abs (FBSL has them all intrinsically, not sure about SB).

Language extension iterators of the (do) and named let kind will come after the basic functionality above has been implemented in the BL vocabulary.

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #710 on: August 24, 2014, 12:49:32 AM »
Hi Rob,

Thank you very much for this additional info. It makes things a little clearer and better ordered in my lamer's mind.

Quote
It may be the pure no-library "syntax" refers to the original Sussman / Steel / etc experiment which I think contained no loop mechanism and in those days was named Schemer - but personally I never would use such , unless in a masochistic mood.

Hehe, no need to go that far. I'll try to add the three iterative features that you described above (in fact, tail recursion is already there with an explicit lambda keyword and one extra pair of parentheses) as soon as I'm through with the yet-missing basic features that I enumerated in my prior post.

Keep the faith! :D
« Last Edit: August 24, 2014, 01:17:39 AM by Mike Lobanovsky »

RobbeK

  • Guest
Re: Lisp in Basic
« Reply #711 on: August 24, 2014, 01:08:16 AM »
Thanks Mike  ;)

Digging deeper :

Intuitively, no space is needed for an active tail call because the
continuation that is used in the tail call has the same semantics
as the continuation passed to the procedure containing the call.
Although an improper implementation might use a new con-
tinuation in the call, a return to this new continuation would
be followed immediately by a return to the continuation passed
to the procedure. A properly tail-recursive implementation re-
turns to that continuation directly.
Proper tail recursion was one of the central ideas in Steele and
Sussman’s original version of Scheme. Their first Scheme in-
terpreter implemented both functions and actors. Control flow
was expressed using actors, which differed from functions in
that they passed their results on to another actor instead of
returning to a caller. In the terminology of this section, each
actor finished with a tail call to another actor.
Steele and Sussman later observed that in their interpreter the
code for dealing with actors was identical to that for functions
and thus there was no need to include both in the language.
A tail call is a procedure call that occurs in a tail con-
text. Tail contexts are defined inductively. Note that a tail
context is always determined with respect to a particular
lambda expression.

---

IMO the (do ) macro can be written, but only of the Scheme contains the quasiquote and the mechisms it is working together, this belongs the (pure) "syntax"

4.2.6. Quasiquotation
(quasiquote hqq templatei) syntax
`hqq templatei syntax
“Backquote” or “quasiquote” expressions are useful for
constructing a list or vector structure when most but not
all of the desired structure is known in advance. If no
commas appear within the hqq templatei, the result of
evaluating `hqq templatei is equivalent to the result of
evaluating ’hqq templatei. If a comma appears within
the hqq templatei, however, the expression following the
comma is evaluated (“unquoted”) and its result is inserted
into the structure instead of the comma and the expres-
sion. If a comma appears followed immediately by an at-
sign (@), then the following expression must evaluate to
a list; the opening and closing parentheses of the list are
then “stripped away” and the elements of the list are in-
serted in place of the comma at-sign expression sequence.
A comma at-sign should only appear within a list or vector
hqq templatei.

and this in combination with :
(let-syntax hbindingsi hbodyi)   syntax

(in combination with syntax-rules ..  I think John already gave the do - maco ; however this syntax is missing here .

best Rob

JRS

  • Guest
Re: Lisp in Basic
« Reply #712 on: August 24, 2014, 01:12:10 AM »
Excellent progress Mike with BL. I'm really liking where this is going!

I can't wait until Charles gets O2 in the ball game.

 

Charles Pegge

  • Guest
Re: Lisp in Basic
« Reply #713 on: August 24, 2014, 02:40:46 AM »
Quote
Quote
... whenever a function calls itself in such a way that the same effect can be implemented by a loop or iteration, Scheme guarantees that the compiler will rewrite it to a loop at the machine-code level, so you will never run out of stack space or need useless time to call procedures when what you try to do can be rewritten to a loop ...
Mike:
(Rob and Charles, I wonder what the algorithm may look like to programmaticaly analyze a Scheme recursive procedure and unroll/fix/recode it automatically into a loop?)

Once a tail recursion is identified, set the params using temp variables as intermediates. Then goto start of the function's inner code body, accumulating the loop results.

O2 Fibo Example:
Code: [Select]
'TAIL RECURSION
===============

function fibo(m,n,c) as string
if c
  return n+" "+fibo(n,m+n,c-1)
end if
end function


'TRANSLATE TO LOOP
==================

function fibo(m,n,c) as string
recur:
if c
  'PARAM SETTING
  tc=c-1 : tn=m+n : tm=n
  m=tm : n=tn : c=tc
  function += n+" "
  goto recur
end if
end function


print fibo 1,1,10

RobbeK

  • Guest
Re: Lisp in Basic
« Reply #714 on: August 24, 2014, 02:53:20 AM »
Thanks Charles,

The Ascii Mandelbrot in BL

----------------------------------------

(define grid '())
(define mapped-grid '())

(define modulus
  (lambda (n d)
     (let (( r (floor (/ n d))))
      (- n (* r d)))))

(define cadr
    (lambda (L)
      (car (cdr L))))

(define sqrt
     (lambda (x)
       (exp (/ (log x) 2))))

(define sq (lambda(x) (* x x)))

(define 1- (lambda (x) (- x 1)))
(define 1+ (lambda (x) (+ x 1)))

(define level
 (lambda (i x y rc ic it orb)
  (if (or (= i it) (> orb 4)) i
    (level (1+ i) (+ rc (- (sq x) (sq y))) (+ ic (* 2 x y)) rc ic it (+ (sq x) (sq y))))))

(define mlevel
   (lambda (L)
     (level 0 (cadr L) (car L) (cadr L) (car L) 11 0)))

(define fill-grid
   (lambda (nrx xo dx nry yo dy matrix dup)
       (if (and (= 0 nrx) (= 0 nry)) matrix
         (if (= 0 nry) (fill-grid (1- nrx) xo dx dup yo dy matrix dup)
           (fill-grid nrx xo dx (1- nry) yo dy
            (cons (list (+ xo (* nrx dx)) (+ yo (* nry dy))) matrix) dup)))))

(define square-grid
   (lambda (nr x y dz)
     (fill-grid (1- nr) (+ x dz) dz nr y dz '() nr)))

(define map-grid
   (lambda (L)
     (map mlevel L)))

(define print*
  (lambda (x)
    (if (> x 9)
      (print x)
      (sequence (print x) (print '" ")) )))

(define print-grid
   (lambda (i it L)
     (if (null? L) T
       (if (= i it) (sequence (print* (car L)) (newline) (print-grid 0 it L))
         (sequence (print* (car L)) (print-grid (1+ i) it (cdr L)))))))

(define main
  (lambda ()
    (set! grid (square-grid 30 -1.7 -2.3 0.1))
    (set! mapped-grid (map-grid grid))
    (print-grid 0 30 mapped-grid)
))

--------------------------------  modulus, and sqrt are not used , they may be removed -----------

any other Ascii "layout" can be done without much effort now ...  the iteration level is decoded in (print* )
..

progr does : makes a grid of coordinates ,  maps the Mandelbrot on every coordinate , makes a grid with the resulting iteration values - prints this list following print* directives ..

best Rob



.
« Last Edit: August 24, 2014, 03:18:08 AM by RobbeK »

JRS

  • Guest
Re: Lisp in Basic
« Reply #715 on: August 24, 2014, 07:46:50 AM »
That's very cool Rob!

Much faster than I was expecting. When it didn't display anything at first, I was ready to head out for a coffee break and before I could get up from my chair the Mandelbrot displayed. This should make Mike happy!

Code: [Select]
jrs@laptop:~/sb/sb22/sblisp/Rob$ time scriba lisp.sb asciiM.bl
SBLisp - Scheme BASIC Lisp

(define grid '())
GRID
(define mapped-grid '())
MAPPED-GRID
(define modulus
  (lambda (n d)
     (let (( r (floor (/ n d))))
      (- n (* r d)))))
MODULUS
(define cadr
    (lambda (L)
      (car (cdr L))))
CADR
(define sqrt
     (lambda (x)
       (exp (/ (log x) 2))))
SQRT
(define sq (lambda(x) (* x x)))
SQ
(define 1- (lambda (x) (- x 1)))
1-
(define 1+ (lambda (x) (+ x 1)))
1+
(define level
 (lambda (i x y rc ic it orb)
  (if (or (= i it) (> orb 4)) i
    (level (1+ i) (+ rc (- (sq x) (sq y))) (+ ic (* 2 x y)) rc ic it (+ (sq x) (sq y))))))
LEVEL
(define mlevel
   (lambda (L)
     (level 0 (cadr L) (car L) (cadr L) (car L) 11 0)))
MLEVEL
(define fill-grid
   (lambda (nrx xo dx nry yo dy matrix dup)
       (if (and (= 0 nrx) (= 0 nry)) matrix
         (if (= 0 nry) (fill-grid (1- nrx) xo dx dup yo dy matrix dup)
           (fill-grid nrx xo dx (1- nry) yo dy
            (cons (list (+ xo (* nrx dx)) (+ yo (* nry dy))) matrix) dup)))))
FILL-GRID
(define square-grid
   (lambda (nr x y dz)
     (fill-grid (1- nr) (+ x dz) dz nr y dz '() nr)))
SQUARE-GRID
(define map-grid
   (lambda (L)
     (map mlevel L)))
MAP-GRID
(define print*
  (lambda (x)
    (if (> x 9)
      (print x)
      (sequence (print x) (print '" ")) )))
PRINT*
(define print-grid
   (lambda (i it L)
     (if (null? L) T
       (if (= i it) (sequence (print* (car L)) (newline) (print-grid 0 it L))
         (sequence (print* (car L)) (print-grid (1+ i) it (cdr L)))))))
PRINT-GRID
(define main
  (lambda ()
    (set! grid (square-grid 30 -1.7 -2.3 0.1))
    (set! mapped-grid (map-grid grid))
    (print-grid 0 30 mapped-grid)
))
MAIN
(main)
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 1
1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 1
1 1 1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 4 4 4 115 4 4 3 3 2 2 2 2 1
1 1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 4 4 4 5 7 9 114 4 3 3 2 2 2 1
1 1 1 1 1 2 3 3 3 3 3 3 3 3 4 4 4 4 5 6 9 118 5 4 4 3 3 3 2 1
1 1 1 1 2 3 3 3 3 3 3 3 3 4 4 4 4 5 6 8 1111116 5 5 4 3 3 3 1
1 1 1 1 2 3 3 3 3 3 3 3 4 4 4 5 7 8 8 101111119 6 6 5 4 3 3 1
1 1 1 2 3 3 3 3 3 3 3 4 4 5 5 6 11111111111111111111114 3 3 1
1 1 1 2 3 3 3 3 3 4 5 5 5 5 6 8 111111111111111111117 5 3 3 1
1 1 1 3 3 3 3 4 5 7 7 7 7 7 7 11111111111111111111119 5 4 3 1
1 1 1 3 4 4 4 5 5 7 111111119 1111111111111111111111116 4 3 1
1 1 1 4 4 4 5 5 6 8 11111111111111111111111111111111115 4 3 1
1 1 1 4 4 6 6 7 1111111111111111111111111111111111118 5 4 3 1
1 1 1111111111111111111111111111111111111111111111117 5 4 3 1
1 1 1 4 4 6 6 7 1111111111111111111111111111111111118 5 4 3 1
1 1 1 4 4 4 5 5 6 8 11111111111111111111111111111111115 4 3 1
1 1 1 3 4 4 4 5 5 7 111111119 1111111111111111111111116 4 3 1
1 1 1 3 3 3 3 4 5 7 7 7 7 7 7 11111111111111111111119 5 4 3 1
1 1 1 2 3 3 3 3 3 4 5 5 5 5 6 8 111111111111111111117 5 3 3 1
1 1 1 2 3 3 3 3 3 3 3 4 4 5 5 6 11111111111111111111114 3 3 1
1 1 1 1 2 3 3 3 3 3 3 3 4 4 4 5 7 8 8 101111119 6 6 5 4 3 3 1
1 1 1 1 2 3 3 3 3 3 3 3 3 4 4 4 4 5 6 8 1111116 5 5 4 3 3 3 1
1 1 1 1 1 2 3 3 3 3 3 3 3 3 4 4 4 4 5 6 9 118 5 4 4 3 3 3 2 1
1 1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 4 4 4 5 7 9 114 4 3 3 2 2 2 1
1 1 1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 4 4 4 115 4 4 3 3 2 2 2 2 1
1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 1
1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 T
(quit)

real 0m35.469s
user 0m35.406s
sys 0m0.028s
jrs@laptop:~/sb/sb22/sblisp/Rob$

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #716 on: August 24, 2014, 08:38:12 AM »
This is REALLY COOL! :D

Rob, thanks A LOT! I'll be back with my update on the progress later on tonight.

.

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #717 on: August 24, 2014, 08:48:48 AM »
Hi Charles,

Once a tail recursion is identified, set the params using temp variables as intermediates. Then goto start of the function's inner code body, accumulating the loop results.

Will this algo apply to any tail recursion case imaginable? Of any complexity and nested depth so that pattern recognition and unrolling can be automated?

Charles Pegge

  • Guest
Re: Lisp in Basic
« Reply #718 on: August 24, 2014, 10:29:21 AM »
Mike,

Complexity is okay as long as it results in single level tail recursion, but other formats could be supported, if the system is smart enough to detect them:

for instance, alternative conditions tail recursion:

function f(...) as ...
if ...
  return f(...)
elseif ...
 return f(...)
else
  ...
end if
end function

JRS

  • Guest
Re: Lisp in Basic
« Reply #719 on: August 24, 2014, 10:50:42 AM »
This is where BL needs to be. IMHO

Code: [Select]
(load-extension "tsx_mysql")

(display "Mysql extension test.")(newline)

(define queries (list
                  "SELECT VERSION(), CURRENT_DATE"
                  "SHOW DATABASES"
                  "SELECT  table_name, table_type, engine FROM information_schema.tables"))

(define run-query
  (lambda (sql)
    (let ((result (mysql-query sql)))
      (if result
        (display result)
        (display (mysql-error))))
    (newline)))

(if (mysql-connect "" "" "" "")
    (for-each run-query queries)
    (display (mysql-error)))

(mysql-disconnect)
(newline)