prime pattern 5

http://code.fed.wiki/assets/pages/lambda-talk-in-a-frame/repl.html HEIGHT 9000

{center Copied from prime_pattern 5|http://lambdaway.free.fr/lambdawalks/?view=prime_pattern5} {uncover http://lambdaway.free.fr/lambdawalks/data/gandhi_adami.jpg 100 500 Gandhi is fan of lambdatalk!} _h1 prime pattern {sup 5} -> loops _p Sometimes you know exactly how many times you have to do something. Sometimes you do something while some condition is true. Most of the time, in the first case you will do {b iteration}, in the second case you will do {b recursion}. _h2 1) iteration _p '{lambda talk} comes with a set of functions allowing to iterate easily on words, sentences and arrays. For instance: _ul {code '{S.serie start end step}} returns a sequence of natural numbers from start to end with step, _ul {code '{S.map func words}} applies a function to a sequence of words and returns the resulting sequence, _ul {code '{S.reduce func words}} applies a function to a sequence of words and returns the result. _p Examples _ul even numbers {prewrap '{S.serie 1 50 2} -> {S.serie 1 50 2} } _ul apply underline on each word {prewrap '{S.map u hello brave new world} -> {S.map u hello brave new world} } _ul apply underline on a sequence {prewrap '{S.reduce u hello brave new world} -> {S.reduce u hello brave new world} } _ul a sequence of powers of 2 {prewrap '{S.map {lambda {:i} {pow 2 :i}} {S.serie 1 10}} -> {S.map {lambda {:i} {pow 2 :i}} {S.serie 1 10}} } _ul the product of numbers fom 1 to 100 {prewrap '{S.reduce long_mult {S.serie 1 100}} -> {S.reduce long_mult {S.serie 1 100}} } _ul and using the following function computing random colors {prewrap '{def randcol {lambda {:w} {span {@ style="color:rgb( {round {* {random} 255}}, {round {* {random} 255}}, {round {* {random} 255}})"}:w}}} -> {def randcol {lambda {:w} {span {@ style="color:rgb( {round {* {random} 255}}, {round {* {random} 255}}, {round {* {random} 255}})"}:w}}} } _ul display a sequence of numbers form 1 to 100 in random colors {prewrap '{S.map randcol {S.serie 1 100}} -> {S.map randcol {S.serie 1 100}} } _h2 2) recursion h2 2) recursion _p Recursion is a more {i native & versatile} way to loop in '{lambda talk}. It's a {b divide and conquer} method, you divide the problem into simpler ones until you can solve them. A tree is made of smaller trees ... until you reach trees which are leaves. The answer contains a smaller question and we get a chance to reach an answer. Maybe not. _p We are going to illustrate this approach in several examples increasing in complexity. _h3 2.1) words & sentences _p '{lambda talk} is basically a text rewriting tool, it loves words and sentences and comes with a small set of functions allowing to play with. {prewrap WORD: [11] [W.equal?, W.empty?, W.length, W.get, W.first, W.rest, W.last, W.slice, W.reverse, W.sort, W.lib] } {prewrap STRING: [15] [S.equal?, S.empty?, S.length, S.first, S.rest, S.last, S.get, S.slice, S.serie, S.map, S.reduce, S.replace, S.reverse, S.sort, S.lib] } _p In order to introduce recursion we will show how a minimal subset of these functions, [{b W.equal?, W.empty? & S.empty?, W.first & S.first, W.rest & S.rest, W.reverse}] is sufficient to invert all characters in a sentence. _p Let's define a sentence, a sequence of words: {pre '{def S hello brave new world} -> {def S hello brave new world} } {pre '{S} -> {S} } _p Note that {b S} is the name of the sentence and you must embed it inside curly braces to get is value. _p Using {b S.first, S.rest & S.empty?} we extract every words manually until the rest is empty {pre '{S.first {S}} -> {S.first {S}} & '{S.empty? {rest {S}}} -> {S.empty? {S.rest {S}}} '{S.first {S.rest {S}}} -> {S.first {S.rest {S}}} & '{S.empty? {S.rest {S.rest {S}}}} -> {S.empty? {S.rest {S.rest {S}}}} '{S.first {S.rest {S.rest {S}}}} -> {S.first {S.rest {S.rest {S}}}} & '{S.empty? {S.rest {S.rest {S.rest {S}}}}} -> {S.empty? {S.rest {S.rest {S.rest {S}}}}} '{S.first {S.rest {S.rest {S.rest {S}}}}} -> {S.first {S.rest {S.rest {S.rest {S}}}}} & '{S.empty? {S.rest {S.rest {S.rest {S.rest {S}}}}}} -> {S.empty? {S.rest {S.rest {S.rest {S.rest {S}}}}}} } _p The previous sequence enlights a pattern leading to a first recursive algorithm: {pre '{def display {lambda {:s} {if {S.empty? {S.rest :s}} then :s else {S.first :s} {display {S.rest :s}}}}} -> {def display {lambda {:s} {if {S.empty? {S.rest :s}} then :s else {S.first :s} {display {S.rest :s}}}}} } {pre '{display {S}} -> {display {S}} } _p Congratulations you just discovered {b recursion}! Note that the {b display} recursive function calls its name in its body. It's the main characteristic of a recursive function, defining it by using it. This pattern is general. _p For instance {b display} can be slightly modified to reverse a sequence of words {pre '{def words_reverse {lambda {:s} {if {S.empty? {S.rest :s}} then :s else {words_reverse {S.rest :s}} {S.first :s}}}} -> {def words_reverse {lambda {:s} {if {S.empty? {S.rest :s}} then :s else {words_reverse {S.rest :s}} {S.first :s}}}} } {pre '{words_reverse {S}} -> {words_reverse {S}} } _p And now, analyzing this function {pre '{def total_reverse {lambda {:s} {if {S.empty? {S.rest :s}} then :s else {total_reverse {S.rest :s}} {W.reverse {S.first :s}}}}} -> {def total_reverse {lambda {:s} {if {S.empty? {S.rest :s}} then :s else {total_reverse {S.rest :s}} {W.reverse {S.first :s}}}}} } _p could you uncrypt the following sentence? {prewrap {total_reverse Welcome in the (lambda way) project, a light framework built on a wiki, (lambda tank), and a functional programming language, (lambda talk) .} } _p We can test if a word belongs to a sequence {pre '{def is? {lambda {:v in :s} {if {S.empty? {S.rest :s}} then false else {if {W.equal? :v {S.first :s}} then true else {is? :v in {S.rest :s}}}}}} -> {def is? {lambda {:v in :s} {if {S.empty? {S.rest :s}} then false else {if {W.equal? :v {S.first :s}} then true else {is? :v in {S.rest :s}}}}}} } {pre '{is? X in a b c d} -> {is? X in a b c d} '{is? b in a b c d} -> {is? b in a b c d} } _p We can apply a function on every word of a sequence {pre '{def apply {lambda {:f :s} {if {S.empty? {S.rest :s}} then {:f {S.first :s}} else {:f {S.first :s}} {apply :f {S.rest :s}}}}} -> {def apply {lambda {:f :s} {if {S.empty? {S.rest :s}} then {:f {S.first :s}} else {:f {S.first :s}} {apply :f {S.rest :s}}}}} } {pre '{apply u {S}} -> {apply u {S}} } {pre '{apply {lambda {:i} [:i]} {S}} -> {apply {lambda {:i} [:i]} {S}} } {pre '{apply {lambda {:i} {span {@ style="text-transform:capitalize; color:#f00;"}:i}} {S}} -> {apply {lambda {:i} {span {@ style="text-transform:capitalize; color:#f00;"}:i}} {S}} } _p And so on. _h3 2.2) numbers _p Our goal is to add the natural numbers from 1 to 100. The ten years old {b Leonard Euler} found a simple formula to get the result, {code n(n-1)/2}, but in this page we explore recursion. So let's invert the sequence and compute the sum of numbers from 100 to 1. We notice that it's 100 plus the sum of numbers from 99 to 1. We can do it again until we reach the sum of 0 and 0 which is 0. We have reached the limit. We can weite this process as a recursive function, using a few useful arithmetic operators [{code +,-,*,/,...,=,<...}] {pre '{def sum {lambda {:n} {if {< :n 1} then 0 // if it's end case sum of 0 is 0 else {+ :n {sum {- :n 1}}}}}} // else add n to the sum of n-1 -> {def sum {lambda {:n} {if {< :n 1} then 0 else {+ :n {sum {- :n 1}}}}}} } {pre '{sum 100} -> 5050 } _p We can't forget the factorial function which is the product of numbers from 1 to n. {pre '{def fac {lambda {:n} {if {< :n 1} then 1 else {* :n {fac {- :n 1}}}}}} -> {def fac {lambda {:n} {if {< :n 1} then 1 else {* :n {fac {- :n 1}}}}}} } {pre '{fac 100} -> 9.33262154439441e+157 } _p It's a huge number beyond the limits of native javascript numbers. But '{lambda talk} comes with a {code long_mult} function allowing to compute huge numbers with an exact precision: {prewrap '{def bigfac {lambda {:n} {if {< :n 1} then 0 else {long_mult :n {bigfac {- :n 1}}}}}} -> {def bigfac {lambda {:n} {if {< :n 1} then 1 else {long_mult :n {bigfac {- :n 1}}}}}} } {prewrap '{bigfac 100} -> 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 } _p But it's another story. _h3 2.3) a game _p I think to a secret number in some ordered interval [0,1,2,...,n] and I ask you to find it. There are several approaches: _p wait & see ... _h3 2.4) graphics _p In the following two last examples, we use iteration to plot curves and recursion to draw tress. _h4 2.4.1) plotting curves _p We give an illustration of what can be done with SVG and parametric curves, for instance this {i gentle one} written using complex exponential functions, thank to Leonard Euler, that great mathematician who discovered {b E = {E}} and much more {pre p(t) = e{sup it} + 1/2e{sup A*it} + i/3e{sup B*it} } _p where A and B are random integers in the range {code [0,10]} - currently {code {def A {floor {* 10 {random}}}} = {A} and {def B {floor {* 5 {random}}}} = {B}}. The complex parametric function can be splitted into two real components {code x(t) and y(t)} {pre -> x(t) = cos(t) + 1/2*cos(A*t) - 1/3*sin(B*t) -> y(t) = sin(t) + 1/2*sin(A*t) + 1/3*cos(B*t) } _p and translated into '{lambda talk} code {pre '{def CYCLIC {lambda {:t} {* 150 {+ {cos :t} // 150 is a scale factor {* {/ 1 2} {cos {* {A} :t}}} {* {/ 1 -3} {sin {* -{B} :t}}}}} {* 150 {+ {sin :t} // 150 is a scale factor {* {/ 1 2} {sin {* {A} :t}}} {* {/ 1 3} {cos {* -{B} :t}}}}} }} -> {def CYCLIC {lambda {:t} {* 150 {+ {cos :t} {* {/ 1 2} {cos {* {A} :t}}} {* {/ 1 -3} {sin {* -{B} :t}}}}} {* 150 {+ {sin :t} {* {/ 1 2} {sin {* {A} :t}}} {* {/ 1 3} {cos {* -{B} :t}}}}} }} } _p The CYCLIC function depends on one parameter, {code t}, which will take its values in some interval, say [{code -10,+10}] by steps of {code 0.05}. The iterative approach is the most appropriated and we will use the couple {code map serie} functions. We can now define a SVG context, some AXES function to apply the required translations and scales, and feed points of a polyline {pre '{def AXES {lambda {:w :h} {@ transform="translate({/ :w 2},{/ :h 2}) scale(1,-1)"} {line {@ x1="-{/ :w 2}:w" y1="0" x2="{/ :w 2}" y2="0" stroke="red" fill="transparent"}} {line {@ x1="0" y1="-{/ :h 2}" x2="0" y2="{/ :h 2}" stroke="green" fill="transparent"}} }} -> {def AXES {lambda {:w :h} {@ transform="translate({/ :w 2},{/ :h 2}) scale(1,-1)"} {line {@ x1="-{/ :w 2}:w" y1="0" x2="{/ :w 2}" y2="0" stroke="red" fill="transparent"}} {line {@ x1="0" y1="-{/ :h 2}" x2="0" y2="{/ :h 2}" stroke="green" fill="transparent"}} }} } {pre '{svg {@ width="580px" height="580px"} {g {AXES 580 580} {polyline {@ points="{S.map CYCLIC {S.serie -10 10 0.01}}" stroke="#222" fill="transparent" stroke-width="4"}}}} } _p to display {svg {@ width="580px" height="580px"} {g {AXES 580 580} {polyline {@ points="{S.map CYCLIC {S.serie -10 10 0.05}}" stroke="#222" fill="transparent" stroke-width="4"}}}} {center {i The cyclic curve drawn with A = {A} and B = {B}.}} _h4 2.4.2) drawing tree structures _p We will define a recursive function {b tree} to draw a kind of tree structure with flowers at the end of branchs. {pre '{def tree {lambda {:e :s :k :a :b} {if {< :s :e} then T-30 M:s T120 M:s T120 M:s T150 // the flower else M:s T:a {tree :e {* :k :s} :k :a :b} T-{+ :a :b} {tree :e {* :k :s} :k :a :b} T:b M-:s }}} -> {def tree {lambda {:e :s :k :a :b} {if {< :s :e} then T-30 M:s T120 M:s T120 M:s T150 else M:s T:a {tree :e {* :k :s} :k :a :b} T-{+ :a :b} {tree :e {* :k :s} :k :a :b} T:b M-:s }}} } _p For instance, {b '{tree 25 50 {/ 2 3} 45 45}} produces this sequence of moves {b M} & turns {b T} {prewrap {tree 25 50 {/ 2 3} 45 45} } _p Using the {code turtle} primitive we will translate moves and turns into SVG points and gather the {b points} attribute of a polyline in a SVG container {pre points = "'{turtle 300 590 180 {tree 25 50 {/ 2 3} 45 45}}" } _p Writing {pre '{tree 5 200 {/ 2 3} 40 4} -> red tree '{tree 5 180 {/ 2 3} 40 10} -> green tree '{tree 5 180 {/ 2 3} 4 20} -> blue tree '{tree 5 150 {/ 2 3} 4 50} -> black tree } _p displays: {svg {@ width="600px" height="600px" style="margin-left:-12px;"} {polyline {@ points="{turtle 340 590 180 {tree 5 200 {/ 2 3} 40 4}}" fill="transparent" stroke="red" stroke-width="1"}} {polyline {@ points="{turtle 340 590 180 {tree 5 180 {/ 2 3} 40 10}}" fill="transparent" stroke="green" stroke-width="1"}} {polyline {@ points="{turtle 340 590 180 {tree 5 180 {/ 2 3} 4 20}}" fill="transparent" stroke="blue" stroke-width="1"}} {polyline {@ points="{turtle 340 590 180 {tree 5 150 {/ 2 3} 4 50}}" fill="transparent" stroke="black" stroke-width="1"}} } {center {i This is not a picture, it's a drawing, you can zoom in.}} _h3 conclusion _p All examples shown in this page are {b live}, the code is active and can be edited. Safely. Code snippets are not tested elsewhere in a {b programming console}, in another {i Interactive Development Environment}. Everything is computed and drawn in real time in this page and the page is written, structured and enriched using the same syntax. Yes, we can't boldify some words as we use to do in modern text editors, simply mouse selecting them and clicking on some {b [B]} bold button, we must {b write} curly braces around them and {b write} the character {b b} appended to the first one, that looks like coming back to the first age of computers, that looks stupid. But doing that we are gently introduced to a powerful syntax leading us to rich constructions, opening a window to the world of code. _p See fromroots2canopy, coding, rewriting as computation|?view=oops, binary numbers|?view=oops6, maxwell_equations, ... _p You are welcome in the '{lambda way} project. You could begin reading the general introduction in home page|../lambdaspeech/?view=start of this project. Slowly. _p {i Alain Marty 2019/11/11 update 2021/11/26} {style ;; pre { box-shadow:0 0 8px #000; padding:5px; } }